The present invention relates to digital communication, and more particularly to an interleaver for reducing the effects of burst errors in a digital communication system.
The communication of digital signals will invariably result in transmission errors, even in systems designed to reduce the frequency of occurrence of such errors. The errors are caused by many well known factors, including noise and other imperfections in the transmission channel.
In order to cope with transmission errors, error correcting codes such as block codes have been developed. A block code is a mapping of K input binary symbols into L output binary symbols. Since L is greater than K, the code can be Selected to provide redundancy, such as parity bits, which are used by a decoder to provide some error detection and error correction ability. The design and implementation of error correcting codes is well known in the art, and a discussion of the subject can be found in G. C. Clark and J. B. Cain, "Error-Correction Coding for Digital Communications," Plenum Press, New York, 1981.
Any error correcting code is limited by the number of consecutive errors that it can detect and/or correct. Thus, "burst errors" comprising a relatively large number of consecutive errors are particularly troublesome for a digital communication system. A solution to the burst error problem is to interleave the data to be communicated prior to transmission such that a burst error affecting a succession of interleaved data symbols will be spread apart when the symbols are deinterleaved at a receiver. Thus, by interleaving an encoder output sequence prior to transmission and deinterleaving the sequence prior to decoding, burst errors are distributed more uniformly at the decoder input.
An interleaver is a device that rearranges (or permutes) the ordering of a sequence of symbols in a deterministic manner. The corresponding deinterleaver at the receiver applies the inverse permutation to restore the sequence of transmitted symbols to its original order. Such interleavers are typically placed externally with respect to the coder/decoder circuits used for error detection and correction. However, certain decoder structures are known in which interleaving can be applied internally in a very simple fashion. An example is a Meggitt-type decoder structure.
One class of interleavers is known as periodic interleavers, for which the interleaving permutation is a periodic function of time. Examples are block interleavers, which accept symbols in blocks and perform identical permutations over each block of symbols, and convolutional interleavers which have no fixed block structure, but perform a periodic permutation over a semi-infinite sequence of coded symbols. A block interleaver typically takes the coded symbols and writes them by columns into a matrix with N rows and B columns. The permutation consists of reading these symbols out of the matrix by rows prior to transmission. Such an interleaver is referred to as a (B, N) block interleaver. The deinterleaver performs the inverse operation. Symbols are written into the deinterleaver by rows and read out by columns. Such interleavers are easily implemented with well known digital technology.
In convolutional interleavers, coded symbols are shifted sequentially into a bank of B registers with increasing lengths. With each new code symbol, a commutator switches to a new register and the new code symbol is shifted in while the oldest code symbol in that register is shifted out to the transmission channel. The input and output commutators operate synchronously. The deinterleaver has a similar structure and performs the inverse operation. It will be appreciated that for proper deinterleaving the deinterleaver commutator must be synchronized with the interleaver commutator. The implementation of such an interleaver can be done with a random access memory, rather than with shift registers, simply by implementing the appropriate control of memory access.
The most important characteristics of a convolutional interleaver are:
1. the minimum separation at the interleaver output is B symbols for any two symbols that are separated by less than N symbols at the interleaver input;
2. any burst of b&lt;B errors inserted by the channel will result in single errors at the deinterleaver output separated by at least N symbols;
3. a periodic pattern of single errors spaced by N+1 symbols results in a burst length of B at the deinterleaver output; and
4. the total end-to-end delay is N (B-1) symbols and the memory requirement is N (B-1)/2 in both the interleaver and deinterleaver. This is half the required delay and memory in a block interleaver/deinterleaver. The parameter B is chosen to be larger than the maximum expected length of the burst errors. N is chosen to be larger than the decoding constraint length for convolutional codes.
Even though convolutional interleavers and deinterleavers require only half the memory of block interleavers, a substantial amount of memory is still required in order to implement these devices for practical communication systems. It would therefore be advantageous to provide an interleaver/deinterleaver implementation in which the memory requirements are further reduced. It would be further advantageous to provide an efficient address generator for a convolutional interleaver implemented in random access memory (RAM), which enables a reduction in the amount of RAM required to implement the interleaver/deinterleaver structure.
The present invention provides an interleaver and deinterleaver structure having the aforementioned advantages.